#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "Stack.h"
#include <stdlib.h>
#include <string.h>
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
void QuickSortNonR(int* arr, int left,int right)
{
	Stack st;
	StackInit(&st);
	int keyi = left;
	int prev = left;
	int cur = left+1;
	int tmp = arr[left];
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		left = StackTop(&st);
		StackPop(&st);
		right = StackTop(&st);
		StackPop(&st);
		prev = left;
		cur = left + 1;
		keyi = left;
		tmp = arr[left];
		while (cur <= right)
		{
			if (arr[cur] < tmp && ++prev != cur)
			{
				Swap(&arr[cur], &arr[prev]);
			}
			cur++;
		}
		Swap(&arr[prev], &arr[keyi]);
		keyi = prev;
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);
}


void MergeSort1(int* arr, int* tmp, int left, int right)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	MergeSort1(arr,tmp, left, mid);
	MergeSort1(arr, tmp, mid + 1, right);
	int begin1 = left, begin2 = mid+1>right?right:mid+1;
	int end1 = mid, end2 = right;
	int i = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[left + i] = arr[begin1];
			i++;
			begin1++;
		}
		else
		{
			tmp[left + i] = arr[begin2];
			i++;
			begin2++;
		}
	}
	while (begin1 <= end1)
	{
		tmp[left + i] = arr[begin1];
		i++;
		begin1++;
	}
	while (begin2 <= end2)
	{
		tmp[left + i] = arr[begin2];
		i++;
		begin2++;
	}
	memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}

void MergeSort(int* arr, int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
		return;
	memset(tmp, 0, sizeof(int) * size);
	MergeSort1(arr, tmp, 0, size-1);
	free(tmp);
	tmp = NULL;
}
void Print(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

}

void MergeSort2(int* arr, int* tmp, int size)
{
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i+gap< size; i+=2*gap)
		{
			int begin1 = i;
			int end1 = begin1 + gap - 1;
			int begin2 = end1 + 1;
			//if (begin2 >= size)
			//	continue;
			int end2 = begin2 + gap - 1;
			if (end2 >= size)
			{
				end2 = size - 1;
			}
			int j = 0;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[i + j] = arr[begin1];
					j++;
					begin1++;
				}
				else
				{
					tmp[i + j] = arr[begin2];
					j++;
					begin2++;
				}
			}
			while (begin1 <= end1)
			{
				tmp[i + j] = arr[begin1];
				j++;
				begin1++;
			}
			while (begin2 <= end2)
			{
				tmp[i+j] = arr[begin2];
				j++;
				begin2++;
			}
			memcpy(arr + i, tmp + i, (end2-i + 1) * sizeof(int));
		}
		gap *= 2;
	}
}
void MergeSortNonR(int* arr,int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
		return;
	memset(tmp, 0, sizeof(int) * size);
	MergeSort2(arr, tmp,size);
	free(tmp);
	tmp = NULL;
}

void CountSort(int* arr, int size)
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < size; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int* tmp = (int*)malloc(sizeof(int) * (max - min + 1));
	memset(tmp, 0, sizeof(int) * (max - min + 1));
	for (int i = 0; i < size; i++)
	{
		tmp[arr[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < max - min + 1; i++)
	{
		while (tmp[i] != 0)
		{
			arr[j++] = i + min;
			tmp[i]--;
		}
	}
}
#include <time.h>
int main()
{
	srand((unsigned int)time(NULL));
	//int arr[] = {10,9,8,7,6,5,4,3,2,1};
	int arr[10];
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100 + i;
	}
	int size = sizeof(arr) / sizeof(int);
//	QuickSortNonR(arr, 0,size-1);
//	MergeSort(arr, size);
	MergeSortNonR(arr, size);
	Print(arr, size);
	int tmp[] = { 101,102,104,101,103,104,105,107,103 };
	int size1 = sizeof(tmp) / sizeof(int);
	CountSort(tmp, size1);
	//Print(arr, size);
	Print(tmp, size1);
	return 0;
}